package com.kitty.record.kittyalgorithm.ds.tree;

import java.util.Objects;

/**
 * @author shenshen.qian@amh-group.com
 * @version 0.0.1
 * @date 2022/2/10 14:32
 */
public class MyBinaryTree<T extends Comparable<T>> {

    private BTNode<T> mRoot;


    /**
     * 先序遍历
     */
    public void preOrder() {
        preOrder(mRoot);
    }

    private void preOrder(BTNode<T> tree) {
        if (tree != null) {
            System.out.println("preOrder-key=" + tree.getKey());
            preOrder(tree.getLeft());
            preOrder(tree.getRight());
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(mRoot);
    }

    private void inOrder(BTNode<T> tree) {
        if (tree != null) {
            inOrder(tree.getLeft());
            System.out.println("inOrder-key=" + tree.getKey());
            inOrder(tree.getRight());
        }
    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        postOrder(mRoot);
    }

    private void postOrder(BTNode<T> tree) {
        if (tree != null) {
            postOrder(tree.getLeft());
            postOrder(tree.getRight());
            System.out.println("postOrder-key=" + tree.getKey());
        }
    }

    /**
     * 查找
     *
     * @param key
     * @return
     */
    public BTNode<T> search(T key) {
        return search(mRoot, key);
    }

    private BTNode<T> search(BTNode<T> root, T key) {
        while (root != null) {
            int compare = key.compareTo(root.getKey());
            if (compare > 0) {
                root = root.getRight();
            } else if (compare < 0) {
                root = root.getLeft();
            } else {
                return root;
            }
        }
        return null;
    }

    /**
     * 获取最大值
     *
     * @return
     */
    public T maxKey() {
        BTNode<T> tbtNode = maxTreeNode(mRoot);
        if (Objects.isNull(tbtNode)) {
            return null;
        }
        return tbtNode.getKey();
    }

    private BTNode<T> maxTreeNode(BTNode<T> treeNode) {
        while (treeNode != null) {
            if (treeNode.getRight() == null) {
                return treeNode;
            }

            treeNode = treeNode.getRight();
        }
        return null;
    }

    /**
     * 获取最小值
     *
     * @return
     */
    public T minKey() {
        BTNode<T> tbtNode = minTreeNode(mRoot);
        if (Objects.isNull(tbtNode)) {
            return null;
        }
        return tbtNode.getKey();
    }

    private BTNode<T> minTreeNode(BTNode<T> treeNode) {
        while (treeNode != null) {
            if (treeNode.getLeft() == null) {
                return treeNode;
            }

            treeNode = treeNode.getLeft();
        }
        return null;
    }

    /**
     * 查找前驱
     * 前驱节点说明：一个结点的前驱，是小于X的最大关键字的结点。
     * LP    RP
     * \   /
     * X
     * /   \
     * LS   RS
     * 首先分析前驱：
     * 满足两个条件，
     * 一是要小于当前键值，那么只有LP和LS区可以找。
     * 二要求是其中最大的值。我们知道，对于LP来说，X、LS、RS都属于他的右子树，那么，X、LS和RS都是大于它的。
     * 所以很显然，前驱就是LS中的最大值，即前驱 = 左子树中的最大值。条件是：存在左子树。
     * <p>
     * 不存在左子树只有左父母的情况
     * 那只能在LP上找了，LP也具有两部分，
     * 第一部分是LP的LS，LP的LS虽然满足小于X的条件，但是LP的LS中所有元素都是小于LP的，所以至少也是LP。
     * 还有一部分，LP可能有左父母或者右父母，显然，右父母大于他的所有左子树，包括X，条件一都不满足，显然不行。
     * 左父母小于LP，所以它竞争不过LP。
     * 所以最终结论就是，在只有左父母，没有左子树的情况，前驱 = 左父母的值。
     * <p>
     * 不存在左子树和左父母的情况
     * 那就只剩下右子树和右父母了，显然，右子树肯定不行，它的所有元素都大于X。
     * 那就只能在右父母中找了，毕竟虽然右父母大于它，但是右父母也有左/右父母和右子树。
     * 右父母的右父母，和右子树都不行，都大于右父母本身，更大于X了。
     * 那就只能在右父母的左父母上找了，对于左父母来说，他的右子树全都大于他，即包括X的右父母和X，
     * 所以，此时找到的左父母就是我们的前驱。
     * 所以，不存在左子树和左父母的情况，
     * 前驱 = 右父母的左父母（如果右父母不存在左父母，就一直往上遍历，直至出现左父母）。
     * 分析完毕。
     *
     * @param treeNode
     * @return
     */
    public BTNode<T> predecessor(BTNode<T> treeNode) {
        //存在左子树
        if (!Objects.isNull(treeNode.getLeft())) {
            BTNode<T> left = treeNode.getLeft();
            return maxTreeNode(left);
        }
        //不存在在左子树
        BTNode<T> parent = treeNode.getParent();
        while (parent != null && parent.getLeft() == treeNode) {
            treeNode = parent;
            parent = parent.getParent();
        }
        return parent;
    }

    /**
     * 查找后继
     * 后继节点说明：一个结点的后继，是大于X的最小关键字的结点。
     * LP    RP
     * \   /
     * X
     * /   \
     * LS   RS
     * 分析
     * 满足两个条件
     * 一是大于当前X的健值，那么只有RP和RS；
     * 二是要求是其中的最小值。
     * 当存在右子树的情况下，X的后继节点=RS中的最小值；
     * <p>
     * 当不存在右子树的情况下：
     * 一存在RP
     * RP的LP是小于X的，不符合；RP的RS和RP的RP均大于X，其中最小值就是RP
     * 所以，X的后继节点=RP节点；
     * 二不存在RP
     * 那么只有LP和LS了，LS下的所有节点均小于X，不符合；
     * LP的RP大于X，LP的RP的RP也是大于X
     * 所以，X的后继节点=LP的RP节点；
     * 分析结束
     *
     * @param treeNode
     * @return
     */
    public BTNode<T> successor(BTNode<T> treeNode) {

        //存在右子树
        if (!Objects.isNull(treeNode.getRight())) {
            BTNode<T> right = treeNode.getRight();
            return minTreeNode(right);
        }

        //不存在右子树
        BTNode<T> parent = treeNode.getParent();
        while (parent != null && parent.getRight() == treeNode) {
            treeNode = parent;
            parent = parent.getParent();
        }
        return parent;
    }

    /**
     * 插入key到树中
     *
     * @param key
     */
    public void insert(T key) {
        BTNode<T> node = new BTNode<>(key, null, null, null);
        insert(this, node);
    }

    /**
     * 插入节点到当前二叉树中
     *
     * @param mbt 二叉树
     * @param n   插入的节点
     */
    private void insert(MyBinaryTree<T> mbt, BTNode<T> n) {
        int compare = 0;
        BTNode<T> mRoot = mbt.mRoot;
        BTNode<T> cNode = null;

        while (mRoot != null) {
            cNode = mRoot;
            compare = n.getKey().compareTo(mRoot.getKey());
            if (compare == 0) {
                //相同的key直接返回；
                return;
            } else if (compare > 0) {
                mRoot = mRoot.getRight();
            } else {
                mRoot = mRoot.getLeft();
            }
        }
        //判断是否为第一个节点
        if (Objects.isNull(cNode)) {
            mbt.mRoot = n;
        } else {
            //这一步不是特别清晰的可以回顾一下双向链表的插入操作；
            //将插入节点的父节点关联到二叉树上
            n.parent = cNode;
            //首先再次判断插入节点的key与父节点的大小，然后根据大小将父节点的左子树或者右子树关联到插入的当前节点上
            if (compare == 0) {
                //相同的key直接返回；
                return;
            } else if (compare > 0) {
                cNode.right = n;
            } else {
                cNode.left = n;
            }
        }
    }

    /**
     * 根据key删除节点
     *
     * @param key
     * @return
     */
    public void remove(T key) {
        //根据key找出需要删除的节点信息
        BTNode<T> search = search(key);
        remove(search);
    }

    /**
     * 从当前的树中删除某个节点
     *
     * 删除分析：
     * 分成四种情况来分析
     * 1.首先当删除节点为叶子节点（左子树和右子树都为null）
     * 该节点的父节点的左子树或者右子树为null，同时该节点的父节点为null
     *
     * 2.当删除节点存在右子树，不存在左子树；
     *
     * 3.当删除的节点存在左子树，不存在右子树；
     *
     * 4.当删除的节点即存在右子树也存在左子树；
     * @param n   需要删除的节点
     * @return 返回删除的节点
     */
    private void remove(BTNode<T> n) {

        BTNode<T> parent = n.parent;
        //1.首先当删除节点为叶子节点（左子树和右子树都为null）
        if (Objects.isNull(n.getRight()) && Objects.isNull(n.getLeft())) {
            if (parent.getLeft() == n) {
                parent.left = null;
            } else if (parent.getRight() == n) {
                parent.right = null;
            }
            n.parent = null;
            return;
        }
        //2.当删除节点存在右子树，不存在左子树；
        if (!Objects.isNull(n.getRight()) && Objects.isNull(n.getLeft())) {
            //当前节点的右子树
            BTNode<T> right = n.getRight();
            if (parent.getRight() == n) {
                parent.right = right;
            } else {
                parent.left = right;
            }
            right.parent = parent;
            return;
        }
        //3.当删除的节点存在左子树，不存在右子树；
        if (Objects.isNull(n.getRight()) && !Objects.isNull(n.getLeft())) {
            //当前节点的左子树
            BTNode<T> left = n.getLeft();
            if (parent.getLeft() == n) {
                parent.left = left;
            } else {
                parent.right = left;
            }
            left.parent = parent;
            return;
        }
        //4.当删除的节点既存在右子树也存在左子树；
        //将当前节点的后继节点值与当前节点交换
        //此时又区分多种情况，后继节点存不存在右子树的问题；
        //为什么不考虑左子树呢?当存在左子树情况，那么后继节点就是左子树了；

        //当前节点的后继节点
        BTNode<T> successor = successor(n);

        n.key = successor.getKey();
        BTNode<T> successorParent = successor.getParent();
        if (successor.getRight() == null) {
            //后继节点不存在右子树
            if (successorParent.getLeft() == successor) {
                successorParent.left = null;
            } else {
                successorParent.right = null;
            }
            successor.parent = null;
        } else {
            if (successorParent.getLeft() == successor) {
                successorParent.left = successor.getRight();
            } else {
                successorParent.right = successor.getRight();
            }
            successor.getRight().parent = successorParent;
            successor.parent = null;
            successor.right = null;
        }
    }


    public class BTNode<T extends Comparable<T>> {

        //key值
        private T key;
        //左孩子
        private BTNode<T> left;
        //右孩子
        private BTNode<T> right;
        //父节点
        private BTNode<T> parent;


        public BTNode(T key, BTNode<T> left, BTNode<T> right, BTNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        public T getKey() {
            return key;
        }

        public BTNode<T> getLeft() {
            return left;
        }

        public BTNode<T> getRight() {
            return right;
        }

        public BTNode<T> getParent() {
            return parent;
        }
    }


}
